home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / language / pcl_src.zoo / lap.txt < prev    next >
Text File  |  1990-01-25  |  27KB  |  656 lines
  1. -*- Mode: Text -*-
  2.  
  3. Copyright (c) 1985, 1986, 1987, 1988, 1989 Xerox Corporation.
  4. All rights reserved.
  5.  
  6. Use and copying of this document is permitted.  Any distribution of this
  7. document must comply with all applicable United States export control
  8. laws.
  9.  
  10. Last updated: 6/3/89 by Gregor
  11.               10/26/89 by Gregor -- added :RETURN, removed :ISHIFT
  12.  
  13. This file contains documentation of the PCL abstract LAP code.  Any port
  14. of PCL is required to implement the abstract LAP code interface.  There
  15. is a portable, relatively good performance implementation in the file
  16. lap.lisp, port-specific implementations are in that file as well.
  17.  
  18. The PCL abstract LAP code mechanism exists to provide PCL with a way to
  19. create high-performance method lookup functions.  Using this mechanism,
  20. PCL can produce "LAP closures" which do the method lookup.  By allowing
  21. PCL to specify these closures using abstract LAP code rather that Lisp
  22. code we hope to achieve the following:
  23.  
  24.   * Better runtime performance.  By using abstract LAP code, we
  25.     will get better machine instruction sequences than we would
  26.     from compiling Lisp code. 
  27.  
  28.   * Better load and update time performance.  Because it should
  29.     be possible to "assemble" the LAP code more quickly than
  30.     compiling Lisp code, PCL will spend less time building the
  31.     method lookup code.
  32.  
  33.   * Ability to use PCL without a compiler.  The LAP assembler will
  34.     still be required but this should be much smaller than the full
  35.     lisp compiler.
  36.  
  37. Of course, not all implementations of the LAP code mechanism will
  38. satisfy all of these goals.  The first is the most important.
  39.  
  40. In particular, many PCL ports will use the portable LAP implementation.
  41. KCL will use the portable implementation in all of its ports.  Other
  42. Lisps may have custom LAP implementations for some ports and use the
  43. portable implementation for other ports.
  44.  
  45. Some Lisps will have a custom LAP implementation but will nonetheless
  46. require the compiler to be loaded to generate LAP closure constructors.
  47.  
  48. An important point is why we have chosen to take this route rather than
  49. have each implementation implement the method lookup codes itself.  This
  50. was done because we are, at PARC, just beginning to study cache behavior
  51. for CLOS programs.  As we learn more about this we will want to modify
  52. the caching strategy PCL uses.  This architecture, because it leaves
  53. PCL to implement caching behavior makes it possible to do this.  Once
  54. this study is complete, implementations may want to do their own, ultra
  55. high performance implementations of caching strategies.
  56.  
  57.  
  58.  
  59. Production of LAP closures is a two step process.  In the first step, a
  60. port-specific function is called to take abstract LAP code and produce a
  61. a "lap closure generator".  Lap closure generators are functions which
  62. are called with a set of closure variable values and return a LAP
  63. closure.
  64.  
  65. The intermediary of the lap closure generators provides an important
  66. optimization.  Because it is assumed that producing the LAP closure
  67. generator can take much longer than producing a LAP closure from the
  68. generator, PCL attempts to make only one closure generator for each
  69. sequence of LAP code.  Because of the way PCL generates the LAP code
  70. sequences, this is quite easy for it to do.
  71.  
  72. The rest of this document is divided into six parts.  
  73.  
  74.   * the metatypes std-instance and fsc-instance
  75.  
  76.   * an abstraction for simple vector indices
  77.  
  78.   * important optimizations
  79.  
  80.   * the port specific function for making lap closure generators
  81.  
  82.   * the actual abstract LAP code
  83.  
  84.   * examples
  85.  
  86. *** The metatypes STD-INSTANCE and FSC-INSTANCE ***
  87.  
  88. In PCL, instances with metaclass STANDARD-CLASS are represented using
  89. the metatype STD-INSTANCE.  (Note that in Cinco de Mayo PCL, this
  90. metatype is called IWMC-CLASS.)  Each port must implement this metatype.
  91. The metatype could be implemented by the following DEFSTRUCT.
  92.  
  93.    (defstruct (std-instance 
  94.                 (:predicate std-instance-p)
  95.                 (:conc-name %std-instance-)
  96.                 (:constructor %allocate-std-instance (wrapper slots))
  97.                 (:constructor %allocate-std-instance-1 ())
  98.                 (:print-function print-std-instance))
  99.      (wrapper nil)
  100.      (slots nil))
  101.  
  102.  PCL itself will guarantee correct access to this structure and the
  103.  accessors and constructors.  With this in mind, the following are
  104.  important.
  105.  
  106.  * Being able to type test this structure quickly is critical. See 
  107.    the :STD-INSTANCE-P opcode.
  108.  
  109.  * The allocation functions should compile inline, do no argument
  110.    checking and be as fast as possible.
  111.  
  112.  * The accessor functions should compile inline, do no checking of their
  113.    arguments and be as fast as possible.  SETF of the accessors should
  114.    do the same.
  115.  
  116. The port is also required to implement the metatype FSC-INSTANCE (called
  117. FUNCALLABLE-INSTANCE, or FIN for short, in Cinco de Mayo PCL).  Objects
  118. with this metatype are used, among other things, to implement generic
  119. functions.  These objects have field structure associated with them and
  120. are also functions that can be applied to arguments.  The fields are the
  121. same as those for STD-INSTANCE, the FSC-INSTANCE metatype has
  122. predicates, print-functions, constructors and accessors as follows:
  123.  
  124.   fsc-instance-p
  125.   print-fsc-instance
  126.   %fsc-instance-wrapper
  127.   %fsc-instance-slots
  128.   %allocate-fsc-instance (wrapper slots)
  129.   %allocate-fsc-instance-1 ()
  130.  
  131. In addition, objects of metatype FSC-INSTANCE have a property called the
  132. funcallable instance function.  When an FSC-INSTANCE is applied to
  133. arguments, the funcallable instance function is what is actually called.
  134. The funcallable instance function of an FSC-INSTANCE can be changed
  135. using the function SET-FUNCALLABLE-INSTANCE-FUNCTION.  There is no
  136. mechanism for obtaining the funcallable instance function of an
  137. FSC-INSTANCE.
  138.  
  139. It is possible to implement the FSC-INSTANCE metatype in pure Common
  140. Lisp. A simple implementation which uses lexical closures as the
  141. instances and a hash table to record that the lexical closures are of
  142. metatype FSC-INSTANCE is easy to write.  Unfortunately, this
  143. implementation adds significant overhead:
  144.  
  145.    to generic-function-invocation (1 function call)
  146.    to slot-access (1 function call or one hash table lookup)
  147.    to class-of a generic-function (1 hash-table lookup)
  148.  
  149. In addition, it would prevent the FSC-INSTANCEs from being garbage
  150. collected.  In short, the pure Common Lisp implementation really isn't
  151. practical.
  152.  
  153. Note that previous implementations of FINS were always based on the
  154. lexical closure metatype.  In some ports, that provides poor
  155. performance.  Those ports may want to consider reimplementing to use the
  156. compiled code metatype.  In that implementation strategy, LAP closure
  157. variables would become constants of the compiled code object.
  158.  
  159. The following note from JonL is of interest when working on a FIN
  160. implementation:
  161.  
  162.   Date: Tue, 16 May 89 05:45:56 PDT
  163.   From: Jon L White <jonl@lucid.com>
  164.   
  165.   This isn't a bug in Lucid's compiler -- it's a lurking bug in PCL
  166.   that will "bite" most implementations where different settings of
  167.   the compiler optimization switches will produce morphologically
  168.   different (but of course functionally equivalent) function objects.
  169.   
  170.   The difficulty is in how discriminator codes service cache misses.  
  171.   They  "call out" to (potentially) random functions that will in some 
  172.   cases "smash" the function object that was actually running as the 
  173.   discriminator code.  This is all right providing you don't return to 
  174.   that function frame, but alas ...
  175.    
  176.   I know this is a more extensive problem because the code in the
  177.   port-independent function 'notice-methods-change' goes out of
  178.   its way to do a tail-recursive call to the function that is going
  179.   to smash the possibly-executing discriminator code.  Here is the
  180.   commentary from that code (sic):
  181.   
  182.   ;; In order to prevent this we take a simple measure:  we just
  183.   ;; make sure that it doesn't try to reference our its own closure
  184.   ;; variables after it makes the dcode change.  Th